﻿#define _CRT_SECURE_NO_WARNINGS 1

//动态规划第一题
//01_斐波那契数列模型_第 N 个泰波那契数_C++
//https://leetcode.cn/problems/n-th-tribonacci-number/description/


//第一眼就是跟斐波那契数列的解法类似，采用递归
//然后时间超过限制了
int tribonacci(int n) {
    if (n == 0)
        return 0;
    else if (n == 2 || n == 1)
        return 1;
    else
        return tribonacci(n - 3) + tribonacci(n - 2) + tribonacci(n - 1);
}

//而在C++中，可以用动态规划来解决。
class Solution {
public:
    int tribonacci(int n) {
        //动态规划第一题
        //1.创建dp表
        vector<int> dp(n + 1);

        //处理边界情况，存在越界可能性。
        if (n == 0)
            return 0;
        if (n == 1 || n == 2)
            return 1;

        //2.状态表示方程
        //dp[i] = dp[i-3] + dp[i-2] + dp[i-1]; 
        //3.初始化
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        //4.填表顺序
        for (int i = 3; i <= n; i++)
        {
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        }

        //5.返回值
        return dp[n];
    }
};


//空间优化
class Solution {
public:
    int tribonacci(int n) {
        // 滚动数组优化代码
        // 空间复杂度:O(1)
        // 时间复杂度:O(n)

        // 处理边界情况，存在越界可能性。
        if (n == 0)
            return 0;
        if (n == 1 || n == 2)
            return 1;

        //滚动数组
        int a = 0;
        int b = 1;
        int c = 1;
        int d = 0;

        for (int i = 3; i <= n; i++) {
            d = a + b + c;
            //滚动操作
            a = b;
            b = c;
            c = d;
        }

        // 5.返回值
        return d;
    }
};